package DataStructrue;
//二分查找,实质上是枚举合适的答案,答案在区间上具有单调性
public class Binary {

    public static long f(long[] arr,int mid){
        return arr[mid];
    }

    //寻找满足>tar的最小值或<=tar的最大值的参数
    public static long minGreater(long[] arr,long tar){
        int l=-1,r=arr.length;
        //l与r相邻时,l指向<=tar的最大值,r指向>tar的最小值
        while(l+1<r){
            int mid=(l+r)>>1;
            //如果mid增大,f(mid)减小,需要交换l和r
            if(f(arr,mid)<=tar) l=mid;//如果f(mid)<=tar,则可能为<tar的最大值,或者=tar
            else r=mid;//如果f(mid)>tar,则可能为>tar的最小值
        }
        return r;
    }
    //寻找满足<tar的最大值或>=tar的最小值的参数
    public static long maxLess(long[] arr,long tar){
        int l=-1,r=arr.length;
        //l与r相邻时,l指向<tar的最大值,r指向>=tar的最小值
        while(l+1<r){
            int mid=(l+r)>>1;
            if(f(arr,mid)<tar) l=mid;//如果f(mid)<tar,则可能为<tar的最大值
            else r=mid;//如果f(mid)>=tar,则可能为>tar的最小值,或者=tar
        }
        return l;
    }
    //寻找=tar的参数
    public static long binarySearch(long[] arr,long tar){
        int l=0,r=arr.length-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(f(arr,mid)<tar)
                l=mid+1;
            else if(f(arr,mid)>tar)
                r=mid-1;
            else return mid;
        }
        return -1;
    }
}
